package solution

import (
	"fmt"
	"myleecode/solution/common"
	"strings"
)

// 60. 排列序列
func Leecode60_GetPermutation(n int, k int) string {
	//var result []string
	checked := make([]bool, n)
	var res []int
	var solve func(idx int)
	solve = func(idx int) {
		if idx == n {
			fmt.Println(res)
			return
		}
		for i:=0; i<n; i++ {
			if !checked[i] {
				checked[i] = true
				res = append(res, idx)
				solve(idx+1)
				res = res[:len(res)-1]
				checked[i] = false
			}
		}
	}

	solve(1)
	return ""
}

// 61. 旋转链表，向前移动链表
// 先结环，然后计算出剪切点
func Leecode61_RotateRight(head *common.ListNode, k int) *common.ListNode {
	p := head
	n := 1
	for p.Next != nil {
		n++
		p = p.Next
	}
	// 将线性链表转换为环形链表
	p.Next = head
	if n < k {
		k = k % n
	}
	for i:=n-k; i>0; i-- {
		p = p.Next
	}
	// 剪切
	head = p.Next
	p.Next = nil
	//fmt.Println(p.Val)
	return head
}

// 62. 不同路径
// url: https://leecode-cn.com/problems/unique-paths

// 动态规划
// v[i][j] = v[i-1][j] + v[i][j-1] (i,j start from 1)
func Leecode62_UniquePaths(m int, n int) int {
	matrix := make([][]int, m)
	for i:=0; i<m; i++ {
		matrix[i] = make([]int, n)
	}

	for i:=0;  i<n; i++ {
		matrix[0][i] = 1
	}
	for j:=0; j<m; j++ {
		matrix[j][0] = 1
	}

	for i:=1; i<m; i++ {
		for j:=1; j<n; j++ {
			matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
		}
	}
	return matrix[m-1][n-1]
}

// 62. 不同路径（有障碍）
func Leecode63_UniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	result := make([][]int, m)
	for i:=0; i<m; i++ {
		result[i] = make([]int, n)
	}
	for i:=0; i<m; i++ {
		result[0][i] = 1
	}
	for j:=0; j<n; j++ {
		result[j][0] = 1
	}
	for i:=1; i<m; i++ {
		for j:=1; j<n; j++ {
			if obstacleGrid[i][j] == 0 {
				result[i][j] = result[i-1][j] + result[i][j-1]
			}
		}
	}
	return result[m-1][n-1]
}

// 64. 求最小路径和

func Leecode64_MinPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	for i:=0; i<m; i++ {
		dp[i] = make([]int, n)
	}
	for i:=0; i<m; i++ {
		for j:=0; j<n; j++ {
			// 计算每一步的最小
			if i == 0 && j == 0 {
				continue
			} else if i == 0 {
				grid[i][j] = grid[i][j-1] + grid[i][j]
			} else if j == 0 {
				grid[i][j] = grid[i-1][j] + grid[i][j]
			} else {
				grid[i][j] = common.Min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
			}
		}
	}
	return grid[m-1][n-1]
}

// 65. 判断是否为数字

func Leecode65_IsNumber(s string) bool {
	// DFA 有限状态机
	var check func(c int32) int
	check = func(c int32) int {
		switch c {
		case ' ':
			return 0
		case '+','-':
			return 1
		case '.':
			return 3
		case 'e','E':
			return 4
		default:
			if c >= '0' && c <= '9' {
				return 2
			}
		}
		return -1
	}
	// 状态转换表
	var stateTransfer = [][]int{
		{0,1,6,2,-1,-1},
		{-1,-1,6,2,-1,-1},
		{-1,-1,3,-1,-1,-1},
		{8,-1,3,-1,4,-1},
		{-1,7,5,-1,-1,-1},
		{8,-1,5,-1,-1,-1},
		{8,-1,6,3,4,-1},
		{-1,-1,5,-1,-1,-1},
		{8,-1,-1,-1,-1,-1},
	}
	state := 0
	final := 360 // 0b101101000
	for _, c := range s {
		id := check(c)
		if id < 0 {
			return false
		}
		state = stateTransfer[state][id]
		if state < 0 {
			return false
		}
	}
	return final & (1 << state) > 0
}

// 66. 数组 + 1

func Leecode66_PlusOne(digits []int) []int {
	size := len(digits)
	d := 0
	for i:=size-1; i>=0; i-- {
		v := digits[i]
		if i == size-1 {
			d = (v + 1)/10
			digits[i] = (v+1) % 10
		} else {
			digits[i] = (v + d) % 10
			d = (v + d) / 10
		}
	}
	if d == 1 {
		return append([]int{1}, digits...)
	}
	return digits
}

// 67. 二进制求和
func Leecode67_AddBinary(a string, b string) string {
	// 如果长度不相等，先填充0
	if len(a) < len(b) {
		a = strings.Repeat("0", len(b)- len(a)) + a
	} else if len(a) > len(b) {
		b = strings.Repeat("0", len(a) - len(b)) + b
	}
	fmt.Println(a, b)
	size := len(a)
	result := make([]uint8, size+1)
	d := uint8(0)
	for i:=size-1; i>=0; i-- {
		result[i+1] = ((a[i]-48) + (b[i]-48) +d) % 2 + 48
		d = ((a[i]-48) + (b[i]-48) + d) / 2
	}
	if d == 1 {
		result[0] = '1'
		return string(result)
	}
	return string(result[1:])
}

// 68. 文本左对齐右对齐
func Leecode68_fullJustify(words []string, maxWidth int) []string {
	return []string{}
}

// 69. X的平方根
func Leecode69_mySqrt(x int) int {
	i := 1
	for ;i<(x+1)/2;i++ {
		if i*i > x {
			break
		}
	}
	// 还可以用math包里面的api
	return i-1
}